Predicting product adoption in large%2Dscale social networks.

Combining Behavioral and Social Network Data for Online Advertising.

Visualizing RFM Segmentation.

Lessons and Challenges from Mining Retail E%2DCommerce Data.
Abstract. The architecture of Blue Martini Software’s e-commerce suite has supported data collection, transformation, and data mining since its inception. With clickstreams being collected at the application-server layer, high-level events being logged, and data automatically transformed into a data warehouse using meta-data, common problems plaguing data mining using weblogs (e.g. sessionization and conflating multi-sourced data) were obviated, thus allowing us to concentrate on actual data mining goals. We briefly review the architecture and discuss many lessons learned over the last four years and the challenges still facing us. The lessons and challenges are presented across two dimensions: business-level vs. technical, and throughout the data mining lifecycle stages of data collection, data warehouse construction, business intelligence, and deployment. The lessons and challenges are more widely applicable to data mining domains outside retail e-commerce. Keywords: Data mining, data analysis, business intelligence, web analytics, web mining, OLAP,
Learning DFA from Simple Examples.
We present a framework for learning DFA from simple  examples. We show that efficient PAC learning of DFA is possible if the class of distributions is restricted to  simple distributions where a teacher might choose examples based on the knowledge of the target concept. This answers an open research question posed in Pitt&#039;s seminal paper: Are DFA&#039;s PAC-identifiable if examples are drawn from the uniform distribution, or some other known simple distribution? Our approach uses the RPNI algorithm for learning DFA from labeled examples. In particular, we describe an efficient learning algorithm for exact learning of the target DFA with high probability when a bound on the number of states (N) of the target DFA is known in advance. When N  is not known, we show how this algorithm can be used for efficient PAC learning of DFAs. Introduction  The problem of learning a DFA with the smallest number of states that is consistent with a given sample (i.e., the DFA accepts each positive example and...
Learning DFA from Simple Examples.
We present a framework for learning DFA from simple  examples. We show that efficient PAC learning of DFA is possible if the class of distributions is restricted to  simple distributions where a teacher might choose examples based on the knowledge of the target concept. This answers an open research question posed in Pitt&#039;s seminal paper: Are DFA&#039;s PAC-identifiable if examples are drawn from the uniform distribution, or some other known simple distribution? Our approach uses the RPNI algorithm for learning DFA from labeled examples. In particular, we describe an efficient learning algorithm for exact learning of the target DFA with high probability when a bound on the number of states (N) of the target DFA is known in advance. When N  is not known, we show how this algorithm can be used for efficient PAC learning of DFAs. Introduction  The problem of learning a DFA with the smallest number of states that is consistent with a given sample (i.e., the DFA accepts each positive example and...
On the Relationship between Models for Learning in Helpful Environments.
Abstract. The PAC and other equivalent learning models are widely accepted models for polynomial learnability of concept classes. However, negative results abound in the PAC learning framework (concept classes such as deterministic finite state automata (DFA) are not efficiently learnable in the PAC model). The PAC model’s requirement of learnability under all conceivable distributions could be considered too stringent a restriction for practical applications. Several models for learning in more helpful environments have been proposed in the literature including: learning from example based queries [2], online learning allowing a bounded number of mistakes [14], learning with the help of teaching sets [7], learning from characteristic sets [5], and learning from simple examples [12,4]. Several concept classes that are not learnable in the standard PAC model have been shown to be learnable in these models. In this paper we identify the relationships between these different learning models. We also address the issue of unnatural collusion between the teacher and the learner that can potentially trivialize the task of learning in helpful environments. Keywords: Models of learning, Query learning, Mistake bounded learning, PAC learning, teaching sets, characteristic samples, DFA learning.
On the Relationship between Models for Learning in Helpful Environments.
Abstract. The PAC and other equivalent learning models are widely accepted models for polynomial learnability of concept classes. However, negative results abound in the PAC learning framework (concept classes such as deterministic finite state automata (DFA) are not efficiently learnable in the PAC model). The PAC model’s requirement of learnability under all conceivable distributions could be considered too stringent a restriction for practical applications. Several models for learning in more helpful environments have been proposed in the literature including: learning from example based queries [2], online learning allowing a bounded number of mistakes [14], learning with the help of teaching sets [7], learning from characteristic sets [5], and learning from simple examples [12,4]. Several concept classes that are not learnable in the standard PAC model have been shown to be learnable in these models. In this paper we identify the relationships between these different learning models. We also address the issue of unnatural collusion between the teacher and the learner that can potentially trivialize the task of learning in helpful environments. Keywords: Models of learning, Query learning, Mistake bounded learning, PAC learning, teaching sets, characteristic samples, DFA learning.
Simple DFA are Polynomially Probably Exactly Learnable from Simple Examples.
Efficient learning of DFA is a challenging  research problem in grammatical inference.  Both exact and approximate (in the PAC  sense) identifiability of DFA from examples  is known to be hard. Pitt, in his seminal  paper posed the following open research  problem: &#034;Are DFA PAC-identifiable if examples  are drawn from the uniform distribution,  or some other known simple distribution  ?&#034; (Pitt, 1989). We demonstrate that the  class of simple DFA (i.e., DFA whose canonical  representations have logarithmic Kolmogorov  complexity) is efficiently probably  exactly learnable under the Solomonoff Levin  universal distribution m (wherein an instance  x with Kolmogorov complexity K(x) is sampled  with probability that is proportional to  2  \GammaK(x)  ). The simple distribution independent  learning theorem states that a concept class  is learnable under the universal distribution  m iff it is learnable under the entire class  of simple distributions provided the examples  are drawn accordin...
Data%2DDriven Theory Refinement Using KBDistAl.
. Knowledge based artificial neural networks offer an attractive  approach to extending or modifying incomplete knowledge bases or  domain theories through a process of data-driven theory refinement. We  present an efficient algorithm for data-driven knowledge discovery and  theory refinement using DistAl, a novel (inter-pattern distance based,  polynomial time) constructive neural network learning algorithm. The  initial domain theory comprising of propositional rules is translated into  a knowledge based network. The domain theory is modified using DistAl  which adds new neurons to the existing network as needed to reduce classification  errors associated with the incomplete domain theory on labeled  training examples. The proposed algorithm is capable of handling patterns  represented using binary, nominal, as well as numeric (real-valued)  attributes. Results of experiments on several datasets for financial advisor   and the human genome project indicate that the performance of  th...
DistAl An inter%2Dpattern distance%2Dbased constructive learning algorithm.
Multi-layer networks of threshold logic units offer an attractive framework for the design of pattern classification systems. A new constructive neural network learning algorithm (DistAl) based on inter-pattern distance is introduced.  DistAl constructs a single hidden layer of spherical threshold neurons. Each neuron is designed to exclude a cluster of training patterns belonging to the same class. The weights and thresholds of the hidden neurons are determined directly by comparing the inter-pattern distances of the training patterns. This offers a significant advantage over other constructive learning algorithms that use an iterative (and often time consuming) weight modification strategy to train individual neurons. The individual clusters (represented by the hidden neurons) are combined by a single output layer of threshold neurons. The speed of DistAl  makes it a good candidate for datamining and knowledge acquisition from very large datasets. Results of experiments on several ar...
A Polynominal Time Incremental Algorithm for Learning DFA.

Learning DFA from Simple Examples.
We present a framework for learning DFA from simple  examples. We show that efficient PAC learning of DFA is possible if the class of distributions is restricted to  simple distributions where a teacher might choose examples based on the knowledge of the target concept. This answers an open research question posed in Pitt&#039;s seminal paper: Are DFA&#039;s PAC-identifiable if examples are drawn from the uniform distribution, or some other known simple distribution? Our approach uses the RPNI algorithm for learning DFA from labeled examples. In particular, we describe an efficient learning algorithm for exact learning of the target DFA with high probability when a bound on the number of states (N) of the target DFA is known in advance. When N  is not known, we show how this algorithm can be used for efficient PAC learning of DFAs. Introduction  The problem of learning a DFA with the smallest number of states that is consistent with a given sample (i.e., the DFA accepts each positive example and...
An Incremental Interactive Algorithm for Regular Grammar Inference.
. We present provably correct interactive algorithms for learning  regular grammars from positive examples and membership queries. A  structurally complete set of strings from a language L(G) corresponding to a target regular grammar G implicitly specifies a lattice of finite state automata (FSA) which contains a FSA MG corresponding to G. The lattice is compactly represented as a version-space and MG is identified by searching the version-space using membership queries. We explore the problem of regular grammar inference in a setting where positive examples are provided intermittently. We provide an incremental version of the algorithm along with a set of sufficient conditions for its convergence. 1 Introduction  Regular Grammar Inference [3, 5, 9, 12] is an important machine learning problem with applications in pattern recognition and language acquisition. It is defined as the process of learning an unknown regular grammar (G) given a finite set of positive examples S  +  , possibly...
Constructive Neural Network Learning Algorithms.
Constructive learning algorithms offer an attractive approach for the incremental construction of near-minimal neural-network architectures for pattern classification. They help overcome the need for ad hoc and often inappropriate choices of network topology in algorithms that search for suitable weights in a priori fixed network architectures. Several such algorithms are proposed in the literature and shown to converge to zero classification errors (under certain assumptions) on tasks that involve learning a binary to binary mapping (i.e., classification problems involving binary-valued input attributes and two output categories). We present two constructive learning algorithms MPyramid-real and MTiling-real that extend the pyramid and tiling algorithms, respectively, for learning real to M-ary mappings (i.e., classification problems involving real-valued input attributes and multiple output classes). We prove the convergence of these algorithms and empirically demonstrate their applicability to practical pattern classification problems. Additionally, we show how the incorporation of a local pruning step can eliminate several redundant neurons from MTiling-real networks.
Constructive Neural Network Learning Algorithms.
Constructive learning algorithms offer an attractive approach for the incremental construction of near-minimal neural-network architectures for pattern classification. They help overcome the need for ad hoc and often inappropriate choices of network topology in algorithms that search for suitable weights in a priori fixed network architectures. Several such algorithms are proposed in the literature and shown to converge to zero classification errors (under certain assumptions) on tasks that involve learning a binary to binary mapping (i.e., classification problems involving binary-valued input attributes and two output categories). We present two constructive learning algorithms MPyramid-real and MTiling-real that extend the pyramid and tiling algorithms, respectively, for learning real to M-ary mappings (i.e., classification problems involving real-valued input attributes and multiple output classes). We prove the convergence of these algorithms and empirically demonstrate their applicability to practical pattern classification problems. Additionally, we show how the incorporation of a local pruning step can eliminate several redundant neurons from MTiling-real networks.
An incremental interactive algorithm for grammar inference.

